A microfiche appendix is part of this patent containing 8 microfiche and 400 frames.
The present application relates to a computer input interface system.
The present invention permits users who are unaware of system constraints and who are completely naive regarding computer operation to provide intelligible inputs to a computer system. It also enables experienced users to interact in a clearer and simpler way.
Providing access to computer systems with natural language is a very important step towards the construction of computer systems which are easy to use. However, although "ease of use" is currently a central goal of builders of computer systems, and although research into the construction of natural language interfaces has gone on for over fifteen years (resulting in the construction of many prototype systems), natural language interfaces are not in common use today. The reason for this is that the natural language interfaces that have been constructed to date are quite difficult to use.
This invention solves the problem of providing USABLE natural language interfaces to computer systems. Users need not learn or remember system limitations. Additionally, both implementation time and processing time for natural language interfaces are decreased.
Natural language interfaces that have been constructed employ a grammar which characterizes the class of acceptable input strings. A parser then accesses this grammar to produce a parse tree (or parse trees for ambiguous input) for the input string. This parse tree is then translated into an expression (or set of expressions) which represent the meaning of the input string and which are interpretable by the computer system for which the interface has been built. A wide variety of grammar formalisms and parsing algorithms have been used. Most of these grammar formalisms can, however, be classified under the general heading of augmented context-free grammars. What this means is that the basic grammar rules are rules of a context-free grammar but each context-free rule has, associated with it, augmentations which give the grammar added power. These augmentations generally access attributes (and sometimes values) of the nodes of the context-free rules.
Linguistic theories based on this class of grammars are those of Gazdar (1982), Bresnan and Kaplan (see Kaplan and Bresnan, 1981 and Bresnan, 1982), and Ross and Saenz (see Ross, 1981 and Saenz, 1982). Parsers for constructing natural language interfaces which utilize grammars of this general class are the DIAMOND Parser developed at SRI (see J. Robinson, 1980), the GPSG Parser developed at HP (see Gawron, King, Lamping, Loebner, Paulson, Pullum, Sag, and Wasow, 1982) and many others. Note that this description is neutral between syntactically-based and semantically-based grammars. In general, these (and other) frameworks are adequate for characterizing both classes of grammars.
Natural language parsers are generally based on one of several parsing algorithms that have been employed for parsing context-free grammars (for example, see Earley, 1980, Younger, 1967, Griffiths and Petrick, 1965, and Ross, 1981). First, a context-free parse is performed. Then, the augmentation rules are used. In some systems, a partial context-free parse is done, then whatever augmentations that are relevant to that portion of the parse are done. This procedure is then iterated until a complete parse is found.
A notable exception to this general trend is the TQA System that has been under development for the past ten years at IBM (see Plath, 1975 and Petrick, 1973). It is based on the theory of transformational grammar (see Chomsky, 1965) and it employs, as grammar rules, several hundred inverse transformations. A transformational parser applies relevant transformations to yield a set of parse trees.
The primary application for natural language interfaces has been to natural language database query systems. For all natural language systems, the user has been required to type his question into the keyboard of a computer terminal. When the entire question had been input, the natural language interface began processing the input string. Processing resulted either in an answer to the user's query or a response that indicates that the query was not understood.
As of yet, natural language systems have not been put into common use. This is because the current state of the art is such that all systems that are constructed have many limitations in coverage. That is, they can only understand a small subset of all possible natural language queries. The construction of a system which can understand all (or even a substantial part) of English, or any other natural language, is impossible today. This is likely to remain impossible for many years to come. Thus, in order for current natural language systems to prove useful, the user communities that utilize these systems will have to be able to adapt to system limitations. They will have to learn the limitations of the system and thereby restrict their input to only the subset that can be understood by the system. Unfortunately, users have been unable to learn these limitations and have therefore been unable to successfully utilize language interfaces.
Tennant (1980) performed the first and only extensive evaluation of a natural language interface. This evaluation was performed for the PLANES system, a natural language database query system that accessed a military aircraft maintenance database in natural language. The results of this evaluation show quite clearly why natural language interfaces are not in common use today. About 1/3 of the queries input to the system by users were not understood, even though the task assigned these users was to solve problems that had been specifically designed to correspond to relatively straightforward queries.
Additionally, all of the queries that were input to the system were simple queries, containing about 6 or 7 words. Often this meant that many queries were needed in order to solve each problem assigned the user. More complex queries, which could have greatly reduced the amount of input required, were never attempted, even though the system had the ability to handle some of these. The reason that more complex queries were not attempted appears to be that the high failure rate for the simple queries gave the users little confidence that more complex ones would work. Thus, the users never attempted to formulate complex queries.
A second reason that natural language interfaces are not in common use today is the large amount of time it has traditionally taken to construct a natural language interface. Current technology is such that each interface must be constructed on a case by case basis for each application. Efforts taking from 10 to 30 man years per application are not uncommon. Thus, only applications that can justify such a large expenditure of manpower are candidates for possible applications. However, given the quality of the system that results, the effort has not proven to be worthwhile.
In the present invention, the user is not required to type a well formulated input to the natural language understanding system, but rather is instead presented with a set of menus. The user successively chooses words or phrases (or numbers, etc.) from the menus to construct his input. At any point in the construction of a natural language input sequence by the user, only a subset of the set of menus in active. These menus have white backgrounds with black printing. Inactive menus have dark backgrounds and white printing. The user is only allowed to choose from active (or white) menus. Items are selected from menus by using a mouse. The mouse is moved on the table and a pointer moves in response to this on the screen. When the pointer is over the desired item, that item can be selected by pushing a button on the mouse.
Additionally, at various points in the construction of natural language input, only a subset of the items in a menu will be active. Those items in an active menu that are not active at a particular point will not appear in the menu at that point. Thus, at any particular point in the construction of natural language input, only those words or phrases that could legally come next will be available for the user to select. Thus, sentences which cannot be processed by the natural language system can never be input to the system, giving a 0% failure rate.
The mode of user interaction with the system is a primary novel aspect of this invention. All previous systems required users to type queries and thereby required the user to learn and adapt to the limitations of the natural language system. Because of the users' inability to learn and adapt, high failure rates result, even for simple queries, in traditional systems. Our system solves this serious problem. System limitations are made obvious, and all sentences that can be input are understood.
Thus, it is an object of the present invention to provide a system for interfacing to a computer, which does not require the user to know any computer language whatsoever.
It is a further object of the present invention to provide a computer interface system which does not require large amounts of time for a user to become accustomed to using the interface system.
It is a further object of the present invention to provide a computer interface system which permits natural language inputs, but prevents the user from offering any ill-formed inputs.
It is a further object of the present invention to provide a natural-language understanding computer interface system which does not require a large and complex grammar to be specified.
It is a further object of the present invention to provide a computer interface system, in which users can direct natural language queries to a relational database system without knowing how to type.
According to the present invention there is provided:
1. An interface system for providing formally constrained outputs to a computing system in accordance with the natural language inputs in a predefined natural language subset, which has a predefined correspondence to the set of said formally constrained outputs, received from an unskilled user, said interface system comprising:
output means, for indicating to said user a set of permissible items;
designating means, for designating, under control of said user, a particular item from among those indicated by said output means;
parsing means for cumulatively parsing natural language inputs in the form of sequences of items successively designated by said user through said designating means, and for repeatedly generating and indicating on said output means all permissible items which could immediately follow the currently received sequence of items in accordance with said predefined natural language subset; and
means for translating the parse of a completed input into an executable machine command, in accordance with said predefined correspondence.